#include <stdio.h>
#include <stdlib.h>

// 定义二叉树节点结构体
typedef struct TreeNode {
    int val;
    struct TreeNode *left;
    struct TreeNode *right;
} TreeNode;

// 创建新节点
TreeNode* createNode(int val) {
    TreeNode* newNode = (TreeNode*)malloc(sizeof(TreeNode));
    newNode->val = val;
    newNode->left = NULL;
    newNode->right = NULL;
    return newNode;
}

// 计算二叉树最大宽度的函数
int widthOfBinaryTree(TreeNode* root) {
    if (root == NULL) {
        return 0;
    }

    // 定义队列结构体
    typedef struct QueueNode {
        TreeNode* node;
        int index;
        struct QueueNode* next;
    } QueueNode;

    QueueNode* front = NULL, *rear = NULL;

    // 入队根节点
    QueueNode* newQueueNode = (QueueNode*)malloc(sizeof(QueueNode));
    newQueueNode->node = root;
    newQueueNode->index = 0;
    newQueueNode->next = NULL;
    front = rear = newQueueNode;

    int maxWidth = 1;

    while (front!= NULL) {
        int size = 0;
        int leftMost = front->index;
        int rightMost;
        QueueNode* temp = front;

        // 计算当前层节点个数，并出队
        while (temp!= NULL) {
            size++;
            temp = temp->next;
        }

        for (int i = 0; i < size; i++) {
            TreeNode* node = front->node;
            int index = front->index - leftMost;

            // 出队
            QueueNode* temp = front;
            front = front->next;
            if (front == NULL) {
                rear = NULL;
            }
            free(temp);

            if (i == 0) {
                leftMost = index;
            }
            if (i == size - 1) {
                rightMost = index;
            }

            if (node->left!= NULL) {
                // 入队左子节点
                newQueueNode = (QueueNode*)malloc(sizeof(QueueNode));
                newQueueNode->node = node->left;
                newQueueNode->index = 2 * index + 1;
                newQueueNode->next = NULL;
                if (rear == NULL) {
                    front = rear = newQueueNode;
                } else {
                    rear->next = newQueueNode;
                    rear = newQueueNode;
                }
            }
            if (node->right!= NULL) {
                // 入队右子节点
                newQueueNode = (QueueNode*)malloc(sizeof(QueueNode));
                newQueueNode->node = node->right;
                newQueueNode->index = 2 * index + 2;
                newQueueNode->next = NULL;
                if (rear == NULL) {
                    front = rear = newQueueNode;
                } else {
                    rear->next = newQueueNode;
                    rear = newQueueNode;
                }
            }
        }
        maxWidth = (rightMost - leftMost + 1) > maxWidth? (rightMost - leftMost + 1) : maxWidth;
    }
    return maxWidth;
}

// 测试示例
int main() {
    // 构建一个简单的二叉树
    TreeNode* root = createNode(1);
    root->left = createNode(2);
    root->right = createNode(3);
    root->left->left = createNode(4);
    root->left->right = createNode(5);

    int width = widthOfBinaryTree(root);
    printf("最大宽度为: %d\n", width);

    return 0;
}